package Aleehot100;

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * ClassName: c034
 * Package: Aleehot100
 * Description: 多个有序链表排序
 *
 * @Author BCXJ
 * @Create 2025/6/30 23:51
 * @Version 1.0
 * @Since 1.0
 */
public class c034 {
    public static void main(String[] args) {
        ListNode listNode2 = new ListNode(2);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode6 = new ListNode(6);
        ListNode listNode1 = new ListNode(1);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode3;
        listNode3.next = listNode5;

        listNode2.next = listNode4;
        listNode4.next = listNode6;
        ListNode[] arr = new ListNode[2];
        arr[0] = listNode1;
        arr[1] = listNode2;

        ListNode listNode = mergeKLists(arr);
        System.out.println(listNode);

    }

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static PriorityQueue<ListNode> heap = new PriorityQueue<>(500 * 10000, (l1, l2) -> {
        return l1.val - l2.val;
    });

    public static ListNode mergeKLists(ListNode[] lists) {
        if(null == lists || lists.length == 0) {
            return new ListNode();
        }
        heap.clear();
        for (ListNode list : lists) {
            if(list == null) {
                continue;
            }
            heap.add(list);
        }
        ListNode head = heap.poll(), poll, pre;
        if(head.next != null) {
            heap.add(head.next);
        }
        pre = head;
        // 堆排序
        while(!heap.isEmpty()) {
            poll = heap.poll();
            pre.next = poll;
            if(poll.next != null) {
                heap.add(poll.next);
            }
            pre = poll;
        }
        return head;
    }


}
